package io.zhengsh.vvip.leetcode.divideandconquer;

import io.zhengsh.vvip.leetcode.ListNode;

public class Q25 {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int count = 0;
        // cur 为当前链表移动位置
        while (cur != null && count != k) {
            cur = cur.next;
            count++;
        }

        // 到达反转的阈值
        if (count == k) {
            // 递归
            cur = reverseKGroup(cur, k);
            while (count != 0) {
                count--;

                // 翻转
                ListNode tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        return head;
    }
}
